class Node
{
public:
    int _key;
    int _value;
    Node *_prev;
    Node *_next;

    Node(int key = -1, int value = -1)
    {
        _key = key;
        _value = value;
        _prev  = nullptr;
        _next  = nullptr;
    }
};


class LRUCache 
{
public:
    LRUCache(int capacity)
        : _head(new Node())
        , _size(0)
        , _capacity(capacity)
    {
        _head->_prev = _head;
        _head->_next = _head;
    }
    
    int get(int key) 
    {
        Node *ret = get_node(key);
        return ret ? ret->_value : -1;
    }
    
    void put(int key, int value) 
    {
        // key存在
        Node *ret = get_node(key);
        if(ret)
        {
            ret->_value = value;
            return;
        }


        // 不管满没满，先插入再说，后面代码再处理满的情况
        Node *newNode = new Node(key, value);
        push_front(newNode);
        _m.insert(make_pair(key, newNode));

        if(_m.size() > _capacity)
        {
            // 满了
            // 删除最后一个节点
            Node *tail = _head->_prev;      // 注意最后一个节点是哨兵节点的prev，不是next！！！
            remove(tail);
            _m.erase(tail->_key);
        }
        return;
    }

private:
    map<int, Node*> _m;
    Node *_head;
    int _capacity;

private:
    // 这里写成一些公用方法
    // get()的时候，如果存在，需要尾删+头插

    // 这里尾删写成remove()
    void remove(Node *cur)
    {
        cur->_prev->_next = cur->_next;
        cur->_next->_prev = cur->_prev;
    }

    // 这里头插写成push_front()
    void push_front(Node *node)
    {
        node->_prev = _head;
        node->_next = _head->_next;
        _head->_next->_prev = node;
        _head->_next = node;
    }

    // 其实这里还可以再封装一个函数
    // 因为get()和put()时，如果这个key存在，所处理的动作都是类似的
    // 如果是get()，尾删头插，返回key的value
    // 如果是put()，也是尾删头插，修改key的value
    Node *get_node(int key)
    {
        auto pos = _m.find(key);
        if(pos == _m.end())
            return nullptr;
        
        Node *cur = pos->second;
        remove(cur);
        push_front(cur);
        return cur;
    }


};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */